package com.test.daily.leetcode.y2021.m10.day1016;

import java.util.ArrayList;
import java.util.List;

/**
 * @descriptions: AddOperator
 * @author: Tom
 * @date: 2021/10/16 下午 02:43
 * @version: 1.0
 */
public class Code03_AddOperator {
    public static void main(String[] args) {
        Code03_AddOperator ca = new Code03_AddOperator();
        ca.addOperators("123",6);
    }

    public int length;
    public String num;
    public int target;
    public List<String> ans;

    public List<String> addOperators(String num, int target) {
        this.length = num.length();
        this.num = num;
        this.target = target;
        StringBuilder str = new StringBuilder();
        this.ans = new ArrayList<String>();
        process(str, 0, 0, 0);
        return this.ans;
    }

    public void process(StringBuilder str, int index, long value, long mul) {
        if (index == length) {
            if (value == target) {
                ans.add(str.toString());
            }
            return;
        }
        int signIndex = str.length();
        if (index > 0) {
            str.append('0');
        }
        long val = 0;
        // index == j ||str.charAt(index)!= '0' 要么是同一个, 如果不是同一个,
        // ++j, 先运算再增加, 这里先增加再运算,经测试，j++ 和 ++j都可以通过
        for (int j = index; j < length && (index == j || num.charAt(index) != '0'); ++j) {
            val = 10 * val + (num.charAt(j) - '0');
            str.append(num.charAt(j));
            if (index == 0) {
                process(str, j + 1, val, val);
            } else {
                str.setCharAt(signIndex, '+');
                process(str, j + 1, value + val, val);
                str.setCharAt(signIndex, '-');
                process(str, j + 1, value - val, -val);
                str.setCharAt(signIndex, '*');
                process(str, j + 1, value - mul + val * mul, val * mul);
            }

        }
        str.setLength(signIndex);
    }
}
